package code101_200.code40_50;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个二叉树，返回它的 后序 遍历。
 */
public class _145postOrderTraversal {

    /**
     * 直接写后序遍历代码即可
     * 先序 ： 跟左右
     * 后续 ： 左右跟 = 跟右左+全局反转
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 22.44%     * 的用户
     * 内存消耗：     * 36.6 MB     * , 在所有 Java 提交中击败了     * 58.07%     * 的用户
     *
     * 耗时有点多，试试多一个栈看看效率
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp;
        stack.push(root);
        while (stack.size()!=0){
            temp = stack.pop();
            list.add(temp.val);
            if(temp.left!=null)stack.push(temp.left);
            if(temp.right!=null)stack.push(temp.right);
        }
        int swap;
        int listSize = list.size()-1;
        for (int i = 0; i < list.size()/2; i++) {
            swap = list.get(i);
            list.set(i,list.get(listSize-i));
            list.set(listSize-i,swap);
        }
        return list;
    }

    /**
     * 此方法用两个栈来解决问题
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.5 MB     * , 在所有 Java 提交中击败了     * 78.14%     * 的用户
     * 结论 ： 看来以后用双栈结构
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode temp;
        stack1.push(root);
        while (stack1.size()!=0){
            temp = stack1.pop();
            stack2.push(temp);
            if(temp.left!=null)stack1.push(temp.left);
            if(temp.right!=null)stack1.push(temp.right);
        }
        while (stack2.size()!=0){
            temp = stack2.pop();
            list.add(temp.val);
        }
        return list;
    }

}
